home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / DLG_P.G < prev    next >
Text File  |  1992-12-08  |  9KB  |  343 lines
  1. /*  This is the parser for the dlg version 2
  2.  *  This is a part of the Purdue Compiler Construction Toolset
  3.  *  8/18/90
  4.  *
  5.  *  Will Cohen
  6.  *
  7.  */
  8.  
  9. #header    <<
  10. #include <ctype.h>
  11. #include "dlg.h"
  12. #ifdef MEMCHK
  13. #include "trax.h"
  14. #else
  15. extern char *malloc();
  16. extern char *calloc();
  17. #endif
  18. >>
  19.  
  20. <<
  21. int    action_no = 0;       /* keep track of actions outputed */
  22. int    nfa_allocated = 0; /* keeps track of number of nfa nodes */
  23. nfa_node *nfa_array = NULL;/* root of binary tree that stores nfa array */
  24. nfa_node nfa_model_node;   /* model to initialize new nodes */
  25. set    used_chars;       /* used to label trans. arcs */
  26. set    used_classes;       /* classes or chars used to label trans. arcs */
  27. set    normal_chars;       /* mask to get rid elements that aren't used
  28.                   in set */
  29. int    flag_paren = FALSE;
  30. int    flag_brace = FALSE;
  31. int    mode_counter = 0;  /* keep track of number of %%names */
  32.  
  33. >>
  34.  
  35. #lexaction <<
  36. #include "dlgdef.h"
  37.  
  38. int    func_action;        /* should actions be turned into functions?*/
  39. int    lex_mode_counter = 0;    /* keeps track of the number of %%names */
  40. >>
  41.  
  42. #token "[\r\t\ ]+"    << zzskip(); >>            /* Ignore white */
  43. #token "[\n]"        << zzline++; zzskip(); >>    /* Track Line # */
  44. #token L_EOF        "\@"
  45. #token PER_PER        "\%\%"
  46. #token NAME_PER_PER    "\%\%[a-zA-Z_][a-zA-Z0-9_]*"
  47.         << p_mode_def(&zzlextext[2],lex_mode_counter++); >>
  48. #token ACTION        "\<\<"
  49.         << if (func_action)
  50.             fprintf(OUT,"static void\nact%d()\n{ ", ++action_no);
  51.            zzmode(ACT); zzskip();
  52.         >>
  53. #token GREAT_GREAT    "\>\>"
  54. #token L_BRACE        "\{"
  55. #token R_BRACE        "\}"
  56. #token L_PAR        "\("
  57. #token R_PAR        "\)"
  58. #token L_BRACK        "\["
  59. #token R_BRACK        "\]"
  60. #token ZERO_MORE    "\*"
  61. #token ONE_MORE        "\+"
  62. #token OR        "\|"
  63. #token RANGE        "\-"
  64. #token NOT        "\~"
  65. #token OCTAL_VALUE "\\0[0-7]*"        
  66.     << {int t; sscanf(&zzlextext[1],"%o",&t); zzlextext[0] = t;}>>
  67. #token HEX_VALUE   "\\0[Xx][0-9a-fA-F]+"
  68.     << {int t; sscanf(&zzlextext[1],"%x",&t); zzlextext[0] = t;}>>
  69. #token DEC_VALUE   "\\[1-9][0-9]*"
  70.     << {int t; sscanf(&zzlextext[1],"%d",&t); zzlextext[0] = t;}>>
  71. #token TAB        "\\t"        << zzlextext[0] = '\t';>>
  72. #token NL        "\\n"        << zzlextext[0] = '\n';>>
  73. #token CR        "\\r"        << zzlextext[0] = '\r';>>
  74. #token BS        "\\b"        << zzlextext[0] = '\b';>>
  75. /* NOTE: this takes ANYTHING after the \ */
  76. #token LIT        "\\~[tnrb]"    << zzlextext[0] = zzlextext[1];>>
  77. /* NOTE: this takes ANYTHING that doesn't match the other tokens */
  78. #token REGCHAR        "~[\\]"
  79.  
  80.  
  81. grammar        : << p_head(); func_action = FALSE;>> (ACTION)* start_states
  82.             << func_action = FALSE; p_tables(); p_tail(); >>
  83.             (ACTION)* "@"
  84.         ;
  85.  
  86. start_states    : ( PER_PER do_conversion
  87.           | NAME_PER_PER do_conversion (NAME_PER_PER do_conversion)*)
  88.             PER_PER 
  89.         ;
  90.  
  91. do_conversion    : <<new_automaton_mode(); func_action = TRUE;>>
  92.             rule_list
  93.             <<
  94.                 dfa_class_nop[mode_counter] =
  95.                     relabel($1.l,comp_level);
  96.                 if (comp_level)
  97.                     p_shift_table(mode_counter);
  98.                 dfa_basep[mode_counter] = dfa_allocated+1;
  99.                 make_dfa_model_node(dfa_class_nop[mode_counter]);
  100.                 nfa_to_dfa($1.l);
  101.                 ++mode_counter;
  102.                     func_action = FALSE;
  103.             >>
  104.         ;
  105.  
  106. rule_list    : rule <<$$.l=$1.l; $$.r=$1.r;>>
  107.             (rule
  108.                 <<{nfa_node *t1;
  109.                    t1 = new_nfa_node();
  110.                    (t1)->trans[0]=$$.l;
  111.                    (t1)->trans[1]=$1.l;
  112.                    /* all accept nodes "dead ends" */
  113.                    $$.l=t1; $$.r=NULL;
  114.                    }
  115.                 >>
  116.             )*
  117.         | /* empty */
  118.             <<$$.l = new_nfa_node(); $$.r = NULL;
  119.                warning("no regular expressions", zzline);
  120.             >>
  121.         ;
  122.  
  123. rule        : reg_expr ACTION
  124.             <<$$.l=$1.l; $$.r=$1.r; ($1.r)->accept=action_no;>>
  125.         | ACTION
  126.             <<$$.l = NULL; $$.r = NULL;
  127.               error("no expression for action  ", zzline);
  128.             >>
  129.         ;
  130.  
  131. reg_expr    : and_expr <<$$.l=$1.l; $$.r=$1.r;>>
  132.             (OR and_expr 
  133.                 <<{nfa_node *t1, *t2;
  134.                    t1 = new_nfa_node(); t2 = new_nfa_node();
  135.                    (t1)->trans[0]=$$.l;
  136.                    (t1)->trans[1]=$2.l;
  137.                    ($$.r)->trans[1]=t2;
  138.                    ($2.r)->trans[1]=t2;
  139.                    $$.l=t1; $$.r=t2;
  140.                   }
  141.                 >>
  142.             )*
  143.         ;
  144.  
  145. and_expr    : repeat_expr <<$$.l=$1.l; $$.r=$1.r;>>
  146.             (repeat_expr <<($$.r)->trans[1]=$1.l; $$.r=$1.r;>>)*
  147.         ;
  148.  
  149. repeat_expr    : expr <<$$.l=$1.l; $$.r=$1.r;>>
  150.             { ZERO_MORE
  151.             <<{    nfa_node *t1,*t2;
  152.                 ($$.r)->trans[0] = $$.l;
  153.                 t1 = new_nfa_node(); t2 = new_nfa_node();
  154.                 t1->trans[0]=$$.l;
  155.                 t1->trans[1]=t2;
  156.                 ($$.r)->trans[1]=t2;
  157.                 $$.l=t1;$$.r=t2;
  158.               }
  159.             >>
  160.             | ONE_MORE
  161.             <<($$.r)->trans[0] = $$.l;>>
  162.             }
  163.         | ZERO_MORE
  164.             << error("no expression for *", zzline);>>
  165.         | ONE_MORE
  166.             << error("no expression for +", zzline);>>
  167.         ;
  168.  
  169. expr        :  L_BRACK atom_list R_BRACK
  170.             << $$.l = new_nfa_node(); $$.r = new_nfa_node();
  171.                 ($$.l)->trans[0] = $$.r;
  172.                 ($$.l)->label = set_dup($2.label);
  173.                 set_orin(&used_chars,($$.l)->label);
  174.             >>
  175.         | NOT L_BRACK atom_list R_BRACK
  176.             << $$.l = new_nfa_node(); $$.r = new_nfa_node();
  177.                 ($$.l)->trans[0] = $$.r;
  178.                 ($$.l)->label = set_dif(normal_chars,$3.label);
  179.                 set_orin(&used_chars,($$.l)->label);
  180.             >>
  181.         | L_PAR reg_expr R_PAR
  182.             << $$.l = new_nfa_node(); $$.r = new_nfa_node();
  183.                 ($$.l)->trans[0] = $2.l;
  184.                 ($2.r)->trans[1] = $$.r;
  185.             >>
  186.         | L_BRACE reg_expr R_BRACE
  187.             << $$.l = new_nfa_node(); $$.r = new_nfa_node();
  188.                 ($$.l)->trans[0] = $2.l;
  189.                 ($$.l)->trans[1] = $$.r;
  190.                 ($2.r)->trans[1] = $$.r;
  191.             >>
  192.         | atom
  193.             << $$.l = new_nfa_node(); $$.r = new_nfa_node();
  194.                 ($$.l)->trans[0] = $$.r;
  195.                 ($$.l)->label = set_dup($1.label);
  196.                 set_orin(&used_chars,($$.l)->label);
  197.             >>
  198.         ;
  199.  
  200. atom_list    : << set_free($$.label); >>
  201.             (near_atom <<set_orin(&($$.label),$1.label);>>)*
  202.         ;
  203.  
  204. near_atom    : << register int i;
  205.              register int i_prime;
  206.           >>
  207.           anychar
  208.             <<$$.letter=$1.letter; $$.label=set_of($1.letter);
  209.             i_prime = $1.letter + MIN_CHAR;
  210.             if (case_insensitive && islower(i_prime))
  211.                 set_orel(toupper(i_prime)-MIN_CHAR,
  212.                     &($$.label));
  213.             if (case_insensitive && isupper(i_prime))
  214.                  set_orel(tolower(i_prime)-MIN_CHAR,
  215.                     &($$.label));
  216.             >>
  217.             { RANGE anychar 
  218.                 << for (i=$$.letter; i<= $2.letter; ++i){
  219.                     set_orel(i,&($$.label));
  220.                     i_prime = i+MIN_CHAR;
  221.                     if (case_insensitive && islower(i_prime))
  222.                         set_orel(toupper(i_prime)-MIN_CHAR,
  223.                             &($$.label));
  224.                     if (case_insensitive && isupper(i_prime))
  225.                          set_orel(tolower(i_prime)-MIN_CHAR,
  226.                             &($$.label));
  227.                     }
  228.                 >>
  229.             }
  230.         ;
  231.  
  232. atom        : << register int i_prime;>>
  233.           anychar
  234.           <<$$.label = set_of($1.letter);
  235.             i_prime = $1.letter + MIN_CHAR;
  236.             if (case_insensitive && islower(i_prime))
  237.             set_orel(toupper(i_prime)-MIN_CHAR,
  238.                 &($$.label));
  239.             if (case_insensitive && isupper(i_prime))
  240.              set_orel(tolower(i_prime)-MIN_CHAR,
  241.                 &($$.label));
  242.           >>
  243.         ;
  244.  
  245. anychar        : REGCHAR    <<$$.letter = $1.letter - MIN_CHAR;>>
  246.         | OCTAL_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  247.         | HEX_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  248.         | DEC_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  249.         | TAB        <<$$.letter = $1.letter - MIN_CHAR;>>
  250.         | NL        <<$$.letter = $1.letter - MIN_CHAR;>>
  251.         | CR        <<$$.letter = $1.letter - MIN_CHAR;>>
  252.         | BS        <<$$.letter = $1.letter - MIN_CHAR;>>
  253.         | LIT        <<$$.letter = $1.letter - MIN_CHAR;>>
  254.         /* NOTE: LEX_EOF is ALWAYS shifted to 0 = MIN_CHAR - MIN_CHAR*/
  255.         | L_EOF        <<$$.letter = 0;>>
  256.         ;
  257.  
  258. <</* empty action */>>
  259.  
  260. #lexclass ACT
  261. #token "@"    << error("unterminated action", zzline); zzmode(START); >>
  262. #token ACTION "\>\>"
  263.         << if (func_action) fprintf(OUT,"}\n\n");
  264.            zzmode(START);
  265.         >>
  266. #token "\>"        << putc(zzlextext[0], OUT); zzskip(); >>
  267. #token "\\\>"        << putc('>', OUT); zzskip(); >>
  268. #token "\\"        << putc('\\', OUT); zzskip(); >>
  269. #token "\n"        << putc(zzlextext[0], OUT); ++zzline; zzskip(); >>
  270. #token "~[\>\\@\n]+"    << fprintf(OUT, "%s", &(zzlextext[0])); zzskip(); >>
  271.  
  272. <<
  273. /* finds nfa state i in the binary tree nfa_array */
  274. nfa_node *index_nfa(i)
  275. register int i;
  276. {
  277.     register nfa_node *p = nfa_array;
  278.  
  279.     if (i){
  280.         while((i>1) && p){
  281.             if(i & 1)
  282.                 p = p->right;
  283.             else
  284.                 p = p->left;
  285.             i = i\>\>1;
  286.         }
  287.         return p;
  288.     }else{
  289.         return NIL_INDEX;
  290.     }
  291. }
  292.  
  293.  
  294. /* adds a new nfa to the binary tree and returns a pointer to it */
  295. nfa_node *new_nfa_node()
  296. {
  297.     register nfa_node *p = nfa_array;
  298.     nfa_node *t;
  299.     register int i;
  300.  
  301.     i = ++nfa_allocated;
  302.  
  303.     t = (nfa_node*) malloc(sizeof(nfa_node));
  304.     *t = nfa_model_node;
  305.     t->node_no = i;
  306.  
  307.     while((i>3) && p){
  308.         if(i & 1)
  309.             p = p->right;
  310.         else
  311.             p = p->left;
  312.         i = i\>\>1;
  313.     }
  314.     if (nfa_allocated == 1)
  315.         nfa_array = t;
  316.     else if (p != NIL_INDEX){
  317.         if (i & 1)
  318.             p->right = t;
  319.         else
  320.             p->left = t;
  321.     }
  322.     else{
  323.         internal_error("%s(%d): missing node on binary tree\n",
  324.             __FILE__,__LINE__);
  325.     }
  326.     return t;
  327. }
  328.  
  329. /* initialize the model node used to fill in newly made nfa_nodes */
  330. make_nfa_model_node()
  331. {
  332.     nfa_model_node.left = NULL;
  333.     nfa_model_node.right = NULL;
  334.     nfa_model_node.node_no = -1; /* impossible value for real nfa node */
  335.     nfa_model_node.nfa_set = 0;
  336.     nfa_model_node.accept = 0;   /* error state default*/
  337.     nfa_model_node.trans[0] = NULL;
  338.     nfa_model_node.trans[1] = NULL;
  339.     nfa_model_node.label = empty;
  340.  
  341. }
  342. >>
  343.